package org.acghub.common.topology;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @Project demos
 * @Package org.acghub.common.topology
 * @Desc
 * @Author Administrator
 * @Date 2025/7/16/星期三 19:33
 * @Version 1.0
 */
public class DAGTopologyGraph<T> implements TopologyGraph<T> {

    private final DAGCircleFinder<T> circleFinder;

    private final Map<DegreeType, Map<T, Integer>> degrees = new HashMap<>();

    private final Set<T> isolatedNodes = new LinkedHashSet<>();

    public DAGTopologyGraph(DAGCircleFinder<T> circleFinder) {
        this.circleFinder = circleFinder;
    }

    public DAGTopologyGraph() {
        this.circleFinder = new DAGCircleFinder<>();
    }


    @Override
    public void addEdge(T from, T to) {
        circleFinder.addEdge(from, to);
        addDegree0(from, DegreeType.OUT, 1);
        addDegree0(from, DegreeType.IN, 0);
        addDegree0(to, DegreeType.IN, 1);
        addDegree0(to, DegreeType.OUT, 0);
        // 自动把孤立节点移除
        removeIsolatedNode0(from);
        removeIsolatedNode0(to);
    }

    @Override
    public boolean removeEdge(T from, T to) {
        if (!circleFinder.removeEdge(from, to)) {
            return false;
        }
        minusDegree0(from, DegreeType.OUT);
        minusDegree0(to, DegreeType.IN);
        return true;
    }

    @Override
    public FindCircleResp<T> findCircle() {
        return circleFinder.findCircle();
    }

    @Override
    public List<T> getNodes(DegreeType degreeType, int degree) {
        return degrees.getOrDefault(degreeType, new HashMap<>()).entrySet().stream().filter(e -> e.getValue() == degree).map(Map.Entry::getKey).toList();
    }

    @Override
    public List<T> getNeighbors(T node) {
        List<T> neighbors = circleFinder.getAdj().get(node);
        if (neighbors == null) {
            return Collections.emptyList();
        }
        return new ArrayList<>(neighbors);
    }

    @Override
    public List<T> getNeighbors(T node, DegreeType degreeType, int degree) {
        return getNeighbors(node).stream().filter(n -> degrees.getOrDefault(degreeType, Collections.emptyMap()).getOrDefault(n, -1) == degree).collect(Collectors.toList());
    }

    @Override
    public void addIsolatedNode(T node) {
        addIsolatedNode0(node);
    }

    @Override
    public boolean removeIsolatedNode(T node) {
        return removeIsolatedNode0(node);
    }

    @Override
    public List<T> topologyQueue(Comparator<T> comparator) {
        return topologyQueue0(comparator);
    }

    @Override
    public void walk(TopologyWalkable<T> walkable, Comparator<T> walkComparator) {
        walk0(walkable, walkComparator);
    }

    /**
     * 核心步骤：
     * 构建邻接表和入度表
     * 将所有入度为0的节点入队
     * BFS遍历：出队节点加入结果，减少邻居入度，新入度为0则入队
     * 检查结果节点数是否等于总节点数（检测环）
     */
    private List<T> topologyQueue0(Comparator<T> comparator) {
        final List<T> topologyQueue = new ArrayList<>();
        final Map<T, Integer> inDegrees = new HashMap<>(degrees.getOrDefault(DegreeType.IN, Collections.emptyMap()));
        // 0.把孤立节点加进去
        for (T isolatedNode : isolatedNodes) {
            inDegrees.put(isolatedNode, 0);
        }
        while (!inDegrees.isEmpty()) {
            // 1.找到入度为0的节点
            List<T> zeroInDegreeNodes = new ArrayList<>();
            for (Iterator<Map.Entry<T, Integer>> ite = inDegrees.entrySet().iterator(); ite.hasNext(); ) {
                Map.Entry<T, Integer> entry = ite.next();
                // 入度为0,代表没有依赖了
                if (entry.getValue() == 0) {
                    zeroInDegreeNodes.add(entry.getKey());
                    ite.remove();
                }
            }

            // 2.减少邻居入度
            for (T zeroInDegreeNode : zeroInDegreeNodes) {
                for (T neighbor : getNeighbors(zeroInDegreeNode)) {
                    int degree = inDegrees.getOrDefault(neighbor, 0);
                    if (degree <= 0) {
                        // 已经遍历过了
                        inDegrees.remove(neighbor);
                    } else {
                        inDegrees.put(neighbor, degree - 1);
                    }
                }
            }

            // 3.将入度为0的节点加入拓扑序列
            if (comparator != null) {
                zeroInDegreeNodes.sort(comparator);
            }
            topologyQueue.addAll(zeroInDegreeNodes);
        }
        return topologyQueue;
    }

    private void addDegree0(T node, DegreeType degreeType, int degree) {
        degrees.computeIfAbsent(degreeType, k -> new HashMap<>()).merge(node, degree, Integer::sum);
    }

    private void minusDegree0(T node, DegreeType degreeType) {
        Map<T, Integer> degreeMap = degrees.get(degreeType);
        if (degreeMap != null) {
            degreeMap.computeIfPresent(node, (k, v) -> v > 0 ? v - 1 : null);
            if (degreeMap.get(node) == null) {
                degreeMap.remove(node);
            }
        }
    }

    private void addIsolatedNode0(T node) {
        isolatedNodes.add(node);
    }

    private boolean removeIsolatedNode0(T node) {
        return isolatedNodes.remove(node);
    }

    private void walk0(TopologyWalkable<T> walkable, Comparator<T> walkComparator) {
        List<T> topologyQueue = topologyQueue0(walkComparator);
        for (T t : topologyQueue) {
            walkable.walk(t, circleFinder.getFather(t));
        }
    }
}
